1. Field of the Invention
The present invention relates generally to a method for using a scanner to scan pixel data from an image on a page and store the scanned pixel data in the memory of a computer, and more particularly to a method for determining the relative position of the each detector element of a detector array over a grid of pixels, thereby facilitating the accurate mapping of scanned pixel data in the computer's memory.
2. Brief Description of the Prior Art
Position sensors or cursor control devices which determine the relative position of a point on a grid and thereby determine the movement of a cursor on a visual display system, such as a computer screen, are known in the art. One such device is an optical position sensor, commonly called a mouse. As used herein, the term "mouse," or its plural "mice," is used to describe any type of mechanical or optical device capable of detecting its relative motion and/or position over a surface and producing an output signal that can be used to determine the position of a cursor on a computer screen or an address in a computer's memory.
In the typical application, a single electro-optical or elctro-mechanical mouse is used in combination with a computer terminal and a software program which allows the operator to enter instructions for a computer without need of a keyboard. Some prior art devices have combined a single mouse with a detector array, capable of detecting pixel data from a scanned surface, to produce a type of scanning device. These types of scanning devices have typically been used to scan a single line of text at a time or other indicia located at some position on the scanned page. The usefulness of such scanners has generally been limited because the mouse used in such applications can only detect motion in one dimension and cannot relate its position on the scanned page to a cursor position.
Another type of prior art scanner, such as the "SkySCAN" Model SCN-101 scanner by Skyworld Technogy, LTD. of Hong Kong, has been utilized to scan a three to four inch wide path of information from a scanned page. However, such scanners are limited because they are also constrained to detecting motion in only one dimension and the recreated images produced by such scanners cannot be combined to form single screens of information, thereby making it impossible to reproduce a standard page of text.
A scanner utilizing two of the above described mice with a detector array is shown in U.S. application Ser. No. 889,130, filed July 23, 1986, now U.S. Pat. No. 4,797,544, which discloses an optical scanner for copying characters on a page and transfering them to the display screen or memory of a computer. Between the scanner and the page is a transparency containing indicia of position, or a grid pattern. The scanner is equipped with an array of photo-sensitive elements for detecting light reflected from the printed characters on the page, but not the transparency. The scanner is also equipped with two optical mice, which are sensitive to light reflected from the transparency and not the page, for determining the position and relative angle of the detector array with respect to the grid pattern.
Each mouse operates as a counter, detecting the number of vertical or horizontal lines crossed on the grid pattern, to determine the position of each mouse with respect to the grid pattern. Although the position of each mouse can be determined, it is also neccessary to determine the exact position of each detector element of the detector array in order to correctly map the scanned data in the memory of the computer. Theoretically, by placing the detector array between the two mice, it is possible to draw a line between the mice and use that line to place the position of each element of the detector array in the memory or display of the computer.
One possible solution for determining where to assign data in the memory of the computer for a straight array of detector elements is to use one of the algorithms typically utilized to determine the coordinates of pixels which lie near a line drawn across a two-dimensional raster grid. These algorithms operate by assigning known coordinates to the ends of the line, determining the slope of the line, and then determining the relative position of the line with respect to the pixels on the grid. The relative position of the line with respect to the grid is determined by making incremental calculations with each step along the line based upon the results of the preceding step.
Bresenham's Line Algorithm is one of the algorithms commonly used to make such calculations because it uses only integer arithmetic and no real variables, thereby eliminating the extra time and hardware required to do arithmetic with real variables. The Bresenham algorithm operates by stepping along the raster grid in the direction of the X-axis, selecting a different pixel coordinate position close to the line for each grid element in the X-axis direction lying below the line segment being mapped. In other words, the Bresenham algorithm calculates a pixel coordinate position for each raster grid element covered by the projection of the line segment onto the X-axis. The algorithm can be referenced to the Y-axis in a manner analogous to the X-axis referencing described hereinabove. In the application to a scanner, the relevant line segment is the array of detectors. Thus, for a detector array having N detector elements, the Bresenham algorithm produces a number of memory assignments equal to N times the cosine of the angle the array makes with the X-axis. But since the scanner detector is sensing data for N pixels and the cosine of an angle is generally less than one, using the Bresenham algorithm in a scanner application is inappropriate because it does not calculate the positions of enough pixels to use the data sensed.
Thus, the problem with using Bresenham's algorithm for determining where to assign scanned data in memory is that when the detector array is alligned at an angle, more memory addresses are selected for storing scanned data than there are corresponding scanned data to be assigned if a proper recreated image is to be produced by the scanner. Since data collected from different positions on the scanned page are always assigned to discrete locations in memory in accordance with this algorithm, scanners using this algorithm to assign scanned data when scanning any line on a page, which was neither parallel nor perpendicular to the vertical or horizontal axis of the page, would recreate an image of the line which is longer than the length of the line actually scanned.
A second type of dual mouse scanner is described in Ichinokawa et al, U.S. Pat. No. 4,581,761, issued Apr. 8, 1986, which shows an image scanner which is randomly movable over the surface of a sheet of paper, which is in turn laying over a pad having magnetostrictive properties. The pad is operative to be subjected to pulses introduced at two adjacent ends of the pad (one end representing the vertical axis and the other end representing the horizontal axis) which cause the magnetostrictive material of the pad to produce wave like disturbances in the surface of the pad which travel in vertical and horizontal directions. The position sensors have the ability to detect the raised portion of the pad when a wave passes thereunder and the ability to determine the position of each sensor with respect to the pad by extrapolating the amount of time required for a wave to reach a position sensor from where it started.
Unlike the absolute position mice described in Ichinokawa et al, optical mice are relative positioning devices which are typically unable to determine their position with respect to the grid pattern unless they are first oriented and initialized before they start counting lines of the grid pattern. Hence, proficient methods must be determined for properly orienting, initializing, and assigning scanned data to memory addresses for the type of dual optical mouse scanner described above.